#include "sort.h"

void InsertSort(int* a,int n){
  for(int i =0; i<n-1; i++){
    int end = i;
    int tmp = a[end+1];
    while(end >=0){
      if(tmp < a[end]){
        a[end+1] = a[end];
      }else{
        break;
      }

      --end;
    }

    a[end+1] = tmp;
  }
}

void PrintArray(int* a,int n){
  for(int i =0; i<n; i++){
    printf("%d ",a[i]);
  }

  printf("\n");
}

void BubbleSort(int* a, int n ){
  for(int i =0; i<n-1; i++){
    for(int j = 0; j<n-1-i; j++ ){
      if(a[j] > a[j+1]){
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
      }
    }
  }
}

void ShellSort(int* a, int n)
{
  int gap = n;
  while(gap > 1){
    gap = gap/3 +1;
    for(int i =0; i<n-gap; i++){
    int end = i;
    int tmp = a[end+gap];
    while(end >= 0){
      if(tmp < a[end]){
        a[end+gap] = a[end];
        end -=gap;
      }else{
        break;
      }
    }

    a[end+gap] = tmp;
  }
  }
}

void Swap(int* pa, int* pb){
  int tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}

void AdjustDown(int* a,int n,int parent)
{
  int child = parent*2+1;
  while(child < n){
    if(child +1 < n && a[child] < a[child+1]){
      child++;
    }

    if(a[child] > a[parent]){
      Swap(&a[child],&a[parent]);
      parent = child;
      child = parent*2+1;
    }else{
      break;
    }
  }
}

void HeapSort(int* a, int n){
  for(int i =(n-2)/2; i>=0; i--){
    AdjustDown(a,n,i);
  }

  int end = n -1;
  while(end > 0){
    Swap(&a[0],&a[end]);
    AdjustDown(a,end,0);
    end--;
  }
}

void SelectSort(int* a, int n){
  int begin =0;
  int end = n-1;
  while(begin < end){
    int mini = begin;
    int maxi = begin;
    for(int i =begin+1;i<=end; i++){
      if(a[i] > a[maxi]){
        maxi = i;
      }

      if(a[i] < a[mini]){
        mini = i;
      }
    }

      Swap(&a[begin],&a[mini]);
      Swap(&a[end],&a[maxi]);
      end--;
      begin++;
  }
}

int GetMidi(int* a, int left,int right)
{
  int mid = (left+right)/2;
  if(a[left] < a[mid]){
    if(a[mid] < a[right]){
      return mid;
    }else if(a[left] < a[right]){
      return right;
    }else {
      return left;
    }
  }else
  {
    if(a[mid] > a[right]){
      return mid;
    }else if(a[left] < a[right]){
      return left;
    }else{
      return right;
    }
  }
}

int PartSort1(int* a,int left, int right){
  int midi = GetMidi(a,left,right);
  Swap(&a[left],&a[midi]);
  
  int keyi = left;
  while(left < right){
    while(left < right && a[right] >= a[keyi]){
      --right;
    }

    while(left < right && a[left] <= a[keyi]){
      ++left;
    }

    Swap(&a[right],&a[left]);
  }

  Swap(&a[left],&a[keyi]);
  return left;
}

int PartSort2(int* a, int left,int right){
  int midi = GetMidi(a,left,right);
  Swap(&a[left],&a[midi]);

  int key = a[left];
  int hole = left;
  while(left < right){
    while(left < right && a[right] >= key){
      --right;
    }
    a[hole] = a[right];
    hole = right;

    while(left < right && a[left] <= key){
      ++left;
    }
    a[hole] = a[left];
    hole = left;
  }

  a[hole] = key;
  return hole;
}

int PartSort3(int* a,int left, int right){
  int midi = GetMidi(a,left,right);
  Swap(&a[midi],&a[left]);

  int prev = left;
  int keyi = left;
  int cur = left+1;
  
  while(cur <= right){
    if(a[cur] <a[keyi] && ++prev != cur){
      Swap(&a[prev],&a[cur]);
    }

    ++cur;
  }

  Swap(&a[keyi],&a[prev]);
  return prev;
}

void QuickSort(int* a, int begin, int end)
{

  if(begin >= end)
    return;

 // int keyi = PartSort1(a,begin,end);
 // QuickSort(a,begin,keyi-1);
 // QuickSort(a,keyi+1,end);


  int keyi = PartSort2(a,begin,end);
  QuickSort(a,begin,keyi-1);
  QuickSort(a,keyi+1,end);
}
